package ds

//Definition for a binary tree node.
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func PreorderTraversal(root *TreeNode) []int {
	res := make([]int, 0)
	s := make([]*TreeNode, 0)
	cur := root
	for cur != nil || len(s) > 0 {
		for cur != nil {
			res = append(res, cur.Val)
			s = append(s, cur)
			cur = cur.Left
		}

		top := s[len(s)-1]
		s = s[:len(s)-1]
		cur = top.Right
	}

	return res
}

func PostorderTraversal(root *TreeNode) []int {
	res := make([]int, 0)
	s := make([]*TreeNode, 0)
	cur := root
	var preNode *TreeNode
	for cur != nil || len(s) > 0 {
		for cur != nil {
			s = append(s, cur)
			cur = cur.Left
		}

		//弹栈的表示左孩子已经处理完了
		top := s[len(s)-1]
		//右孩子为nil或者右孩子已经遍历完了
		if top.Right == nil || top.Right == preNode {
			res = append(res, top.Val)
			s = s[:len(s)-1]
			preNode = top
		} else {
			//让下一个处理的节点为右孩子，必须是cur = top.Right的方式
			cur = top.Right
		}
	}

	return res
}
